//  设计哈希函数, 将传入的字符串哈希化 转换成hashCode
function hashFn (string, limit = 7) {
  const PRIME = 13
  // 1. 定义存储hashCode的变量
  let hashCode = 0
  // 2.计算hashCode的值
  for (const item of string) {
    hashCode = PRIME * hashCode + item.charCodeAt()
  }
  // 3.对hashCode 取余
  return hashCode % limit
}

console.log(hashFn('hyun'));
// 判断一个数是否是质数
function isPrime (number) {
  if (number <= 1 || number === 4) return false
  const temp = Math.ceil(Math.sqrt(number))
  for (let i = 2; i < temp; i++) {
    if (number % i === 0) {
      return false
    }
  }
  return true
}
class HashTable {
  constructor () {
    this.storage = []
    this.count = 0
    this.limit = 7
    // 装填因子(已有个数/总个数)
    this.loadFactor = 0.75
    this.minLoadFactor = 0.25
  }
  getPrime (number) {
    while (!isPrime(number)) {
      number++
    }
    return number
  }
  // 往哈希表里添加数据
  put (key, value) {
    // 1.根据key 获取要映射到storage 里面的index
    const index = hashFn(key, this.limit)
    // 2. 根据index 取出相应的bucket
    let bucket = this.storage[index]
    // 3.判断是否存在bucket
    if (bucket === undefined) {
      bucket = [] // 不存在则创建
      this.storage[index] = bucket
    }
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i]
      if (tuple[0] === key) {
        tuple[1] = value
        return
      }
    }
    bucket.push([key, value])
    this.count++
    if (this.count / this.limit > this.loadFactor) {
      this.resize(this.getPrime(this.limit * 2))
    }
  }
  // 根据get (key) 获取value
  get (key) {
    const index = hashFn(key, this.limit)
    const bucket = this.storage[index]
    if (bucket === undefined) {
      return null
    }
    for (const tuple of bucket) {
      if (tuple[0] === key) {
        return tuple[1]
      }
    }
    return null
  }
  // 删除指定得key
  remove (key) {
    const index = hashFn(key, this.limit)
    const bucket = this.storage[index]
    if (bucket === undefined) {
      return null
    }
    for (let i = 0, len = bucket.length; i < len; i++) {
      const tuple = bucket[i]
      if (tuple[0] === key) {
        bucket.splice(i, 1)
        this.count--
      }
      if (this.limit > 7 && this.count / this.limit < this.minLoadFactor) {
        this.resize(this.getPrime(Math.floor(this.limit / 2)))
      }
      return tuple
    }
  }
  isEmpty () {
    return this.count === 0
  }
  size () {
    return this.count
  }
  resize (newLimit) {
    // 保存旧的storage 数组内容
    const oldStorage = this.storage
    // 2. 重置所有得属性
    this.storage = []
    this.count = 0
    this.limit = newLimit
    // 3.遍历oldStorage, 取出所有数据
    for (const bucket of oldStorage) {
      if (bucket) {
        for (const b of bucket) {
          this.put(b[0], b[1])
        }
      }
    }
  }
}